package com.hy;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created With IntelliJ IDEA.
 * Descriptions: 二叉树最大深度
 * author: Mr.Du
 * Date: 2022/11/12
 * Time: 10:56
 */
public class MaxDepth {
    
    /**
     * 递归
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        if( root == null) return 0;
        int left = maxDepth(root.left) + 1;
        int right = maxDepth(root.right) + 1;
        return Math.max(left,right);
    }
    
    /**
     * 层序遍历统计
     * @param root
     * @return
     */
    public int maxDepth1(TreeNode root){
        if( root == null) return 0;
        int depth = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            depth++;
            for(int i = 0;i < size;i++){
                TreeNode tmp = queue.poll();
                if(tmp.right != null) queue.offer(tmp.right);
                if(tmp.left != null) queue.offer(tmp.left);
            }
        }
        return depth;
    }
}
